package NewCode_CM11;


/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/29 15:43
 */
public class Solution {
    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode partition(ListNode pHead, int x) {
        // write code here
        //准备两个逻辑上的链表
        //ans1: 小于 x
        ListNode ans1 = new ListNode(-1);
        ListNode last1 = ans1;
        //ans2: 大于 x
        ListNode ans2 = new ListNode(-1);
        ListNode last2 = ans2;

        ListNode cur = pHead;
        while (cur!=null){
            ListNode next =cur.next;

            if (cur.val < x){
                cur.next=null;
                last1.next= cur;
                last1 = cur;
            }else {
                cur.next=null;
                last2.next = cur;
                last2 = cur;
            }
            cur = next;
        }

        last1.next = ans2.next;
        return ans1.next;

    }
}
